import collections


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def str2tree(self, s):
        """
        :type s: str
        :rtype: TreeNode
        """
        state = 0
        left_index = 0
        right_index = 0
        n = len(s)
        stack = collections.deque()
        while right_index < n:
            if s[right_index] == '(':
                if right_index > left_index:
                    num = int(s[left_index: right_index])
                    node = TreeNode(num)
                    stack.append(node)
                left_index = right_index + 1
            else:
                if s[right_index] == ')':
                    if right_index > left_index:
                        num = int(s[left_index: right_index])
                        node = TreeNode(num)
                        if not stack[-1].left:
                            stack[-1].left = node
                        else:
                            stack[-1].right = node
                    else:
                        node = stack.pop()
                        if not stack[-1].left:
                            stack[-1].left = node
                        else:
                            stack[-1].right = node
                    left_index = right_index + 1
            right_index += 1

        if right_index > left_index:
            num = int(s[left_index: right_index])
            return TreeNode(num)
        else:
            if not stack:
                return None
            else:
                return stack[0]


data = Solution()
s = "4(2(3)(1))(6(5))"
print(data.str2tree(s))
